1. Field of the Invention
The present invention relates to scheduling of jobs that are being submitted to a processor that is capable of dynamic frequency and voltage scaling (DVFS).
2. Background of the Related Art
Dynamic frequency and voltage scaling (DVFS) techniques have become standard features in present-day multi-core processors. These techniques allow the system or user to vary the frequency and voltage supplied to the processor statically or dynamically, therefore varying the energy spent in computation, at the expense of computational speed. For example, decreasing processor frequency at a fixed voltage allows one to decrease processor power consumption. On the other hand, computational speed is reduced, sometimes proportionately and sometimes in a smaller proportion than the decrease of processor power.
Large scale computing at petaflops and beyond would require programs to run on several hundred thousand to millions of processors. This means that the energy consumed to execute such programs will run into the order of several to tens of megawatts. At this scale, the term “performance” acquires a meaning beyond mere compute speed: “performance” means how intelligently a compute job balances speed with power consumption. To achieve this balance, frequency and voltage scaling techniques become crucial. Some programs can be relatively insensitive to small frequency and voltage variations, during some phase of their execution, and this can be favorably leveraged for an efficient high performance computing run. A lot of research has therefore been conducted into finding DVFS settings that could best trade-off power expenditure against an acceptable computational speed.
Apart from DVFS techniques for processors, investigations have also been carried looking into ways and means of reducing energy consumption by other compute hardware, such as the physical memory, disk drives, network related hardware, and the power supply. All these techniques, while reducing energy consumption, could potentially impact program performance. To generalize, therefore, in the context of the performance of applications running on current and future computing infrastructure, it is necessary to not merely consider computational efficiency, but rather, the energy-compute efficiency trade-off.
A large number of jobs are submitted to a supercomputing facility, or a data center. In order to increase the efficiency of their execution schedule, the technique of backfilling is used along with a typical scheduling algorithm, such as first come first serve (FCFS). Backfilling allows smaller jobs to “pack” into spatio-temporal gaps left by scheduled, finished and running larger jobs, thus improving the overall scheduling performance metric (such as average slowdown, or average completion time).
Parallel programs, when submitted to a data center or a supercomputing center, enter a scheduling queue. As there are other tasks waiting in the queue, or being executed on the computing resource, the submitted program is not immediately executed. Therefore, the time taken to process a submitted compute task is much larger than the run-time of the task itself, and consequently, users do not expect their programs to return quickly. Users therefore inherently allow for a slack in the time of completion and return of their submitted task. This slack itself is typically not fixed, but varies, increasing when the load on the data center is large.
One of the recent and emerging study areas in energy-efficient computing is energy-aware scheduling. DVFS-based energy aware scheduling (or another energy-optimization technique) is applied to jobs submitted in a schedule, the run-time of those jobs will often increase. Some of the approaches taken to mitigate this problem include selecting jobs for which run times are relatively less affected by DVFS, or applying DVFS during low-utilization periods, and to leverage the slack allowed by users due to the load on the data center, given their deadline constraints.